12.9 Once the suffix array is constructed, the short routine shown in Figure 12.50 can be invoked from Figure 12.32 to create the longest common prefix array. a. In the code, what does rank[i] represent? b. Suppose that LCP[rank[i] ] = h. Show that LCP[rank[i+1] ] ≥ h − 1. c. Show that the algorithm in Figure 12.50 correctly computes the LCP array. d. Prove that the algorithm in Figure 12.50 runs in linear time. 1 /* 2 * Create the LCP array from the suffix array 3 * @param s the input array populated from 0..N-1, with available pos N 4 * @param sa the already-computed suffix array 0..N-1 5 * @param LCP the resulting LCP array 0..N-1 6 */ 7 public static void makeLCPArray( int [ ] s, int [ ] sa, int [ ] LCP ) 8 { 9 int N = sa.length; 10 int [ ] rank = new int[ N ]; 11 12 s[ N ] = -1; 13 for( int i = 0; i < N; i++ ) 14 rank[ sa[ i ] ] = i; 15 16 int h = 0; 17 for( int i = 0; i < N; i++ ) 18 if( rank[ i ] > 0 ) 19 { 20 int j = sa[ rank[ i ] - 1 ]; 21 22 while( s[ i + h ] == s[ j + h ] ) 23 h++; 24 25 LCP[ rank[ i ] ] = h; 26 if( h > 0 ) 27 h--; 28 } 29 } | |
| View Solution | |
| << Back | Next >> |